package com.myhome.money.base.datastructure;

import java.util.Stack;

/**
 * @Author: 许路路
 * @Date: 2019/4/15
 */
public class LinkedLists {

    //实现单链表、循环链表、双向链表，支持增删操作
    //实现单链表反转
    //实现两个有序的链表合并为一个有序链表
    //实现求链表的中间节点

    public static void main(String[] args) {
        testSingle();
        System.out.println("1,===========================");
        twoWayTest1();
        System.out.println("2,===========================");
        testCycle1();
        System.out.println("3:===================");
        testCycle2();
    }

    public static void testSingle() {
        SingleList singleList = new SingleList();
        singleList.add(10);
        singleList.add(9);
        singleList.add(7);
        singleList.add(8);
        singleList.add(9);
        singleList.print();
        int mid = singleList.midNode();
        System.out.println("mid:" + mid);
        singleList.reverse();
        singleList.print();
        mid = singleList.midNode();
        System.out.println("mid:" + mid);
        System.out.println("remove:======================");
        singleList.remove(9);
        singleList.remove(5);
        singleList.remove(10);
        singleList.remove(8);
        singleList.remove(8);
        singleList.print();
    }

    public static void testCycle1() {
        CycleList cycleList = new CycleList(1);
        cycleList.add(12);
        cycleList.add(13);
        cycleList.add(14);
        cycleList.print();
        int res = cycleList.remove();
        System.out.println("remove:" + res);
        cycleList.print();
    }

    public static void testCycle2() {
        CycleList cycleList = new CycleList(3);
        cycleList.add(12);
        cycleList.add(13);
        cycleList.add(14);
        cycleList.add(15);
        cycleList.add(16);
        cycleList.print();
        int res = cycleList.remove();
        System.out.println("remove:" + res);
        res = cycleList.remove();
        System.out.println("remove:" + res);
        cycleList.print();
    }

    public static void twoWayTest1() {
        TwoWayList twoWayList = new TwoWayList();
        twoWayList.add2head(1);
        twoWayList.add2head(2);
        twoWayList.add2head(6);
        twoWayList.add2tail(23);
        twoWayList.add2tail(34);
        twoWayList.add2tail(23);
        twoWayList.add2tail(44);
        twoWayList.print();
        int res = twoWayList.removeFirst();
        System.out.println("remove first:" + res);
        res = twoWayList.removeLast();
        System.out.println("remove last:" + res);
        twoWayList.print();
    }

    /**
     * 双向链表
     */
    static class TwoWayList {
        private SingleListNode head;
        private SingleListNode tail;

        public void add2tail(int value) {
            SingleListNode node = new SingleListNode(value, null);
            if (tail == null) {
                head = tail = node;
                return;
            }
            if (tail.getLastNode() == null) {
                head.setNextNode(node);
            } else {
                tail.setNextNode(node);
            }
            node.setLastNode(tail);
            tail = node;
        }

        public void add2head(int value) {
            SingleListNode node = new SingleListNode(value, null);
            if (head == null) {
                head = tail = node;
                return;
            }
            if (tail.getLastNode() == null) {
                tail.setLastNode(node);
            }
            node.setNextNode(head);
            head.setLastNode(node);
            head = node;
        }

        public int removeFirst() {
            if (head == null) {
                throw new IllegalStateException("list is empty!");
            }
            int res = head.getData();
            head = head.getNextNode();
            return res;
        }

        public int removeLast() {
            if (tail == null) {
                throw new IllegalStateException("list is empty!");
            }
            int res = tail.getData();
            tail = tail.getLastNode();
            if (tail != null) {
                tail.setNextNode(null);
            }
            return res;
        }

        public int midNode() {
            return 0;
        }

        public void print() {
            SingleListNode node = head;
            StringBuilder sb = new StringBuilder();
            while (node != null) {
                sb.append(node.getData()).append("-->");
                node = node.getNextNode();
            }
            System.out.println(sb.toString());
        }

    }

    /**
     * 循环链表
     */
    static class CycleList {
        private int size;
        private int count;
        SingleListNode head;
        SingleListNode tail;

        public CycleList(int size) {
            if (size <= 0) {
                throw new IllegalArgumentException("size setting an error value:" + size);
            }
            this.size = size;
            this.count = 0;
            head = tail = null;
        }

        public int midNode() {
            return 0;
        }

        public void add(int value) {
            SingleListNode node = new SingleListNode(value, null);
            if (head == null) {
                head = node;
                tail = head;
                head.setNextNode(tail);
                count++;
                return;
            }
            tail.setNextNode(node);
            tail = node;
            if (count == size) {
                head = head.getNextNode();
            } else {
                count++;
            }
        }

        public int remove() {
            if (count < 1) {
                throw new IllegalStateException("list is empty!");
            }
            int value = head.getData();
            if (count == 1) {
                head = tail = null;
            } else {
                head = head.getNextNode();
            }
            count--;
            return value;
        }

        public void print() {
            if (count < 1) {
                return;
            }
            SingleListNode node = head;
            StringBuilder sb = new StringBuilder();
            while (node != null) {
                sb.append(node.getData()).append(",");
                node = node.getNextNode();
            }
            System.out.println(sb.toString());
        }
    }

    /**
     * 单链表
     */
    static class SingleList {
        SingleListNode head;
        SingleListNode tail;
        int size;

        public int midNode() {
            if (size <= 0) {
                throw new IllegalStateException("链表没有元素");
            }
            int mid;
            if (size % 2 == 0) {
                mid = size / 2;
            } else {
                mid = size / 2 + 1;
            }
            SingleListNode node = head;
            while (--mid > 0) {
                node = node.getNextNode();
            }
            return node.getData();
        }

        public void add(int value) {
            SingleListNode node = new SingleListNode(value, null);
            if (head == null) {
                tail = head = node;
            } else {
                tail.setNextNode(node);
                tail = node;
            }
            size++;
        }

        public void remove(int value) {
            if (size <= 0) {
                return;
            }
            //判断是不是删除头节点
            if (head.getData() == value) {
                head = head.getNextNode();
                size--;
                return;
            }
            //先查找到该节点
            SingleListNode pre = head;
            SingleListNode node = pre.getNextNode();
            while (node != null) {
                if (node.getData() == value) {
                    pre.setNextNode(node.getNextNode());
                    size--;
                }
                pre = node;
                node = node.getNextNode();
            }
        }

        public void reverse() {
            if (size <= 1) {
                return;
            }
            Stack<SingleListNode> stack = new Stack<>();
            SingleListNode node = head;
            while (node != null) {
                stack.push(node);
                node = node.getNextNode();
            }
            head = tail = null;
            size = 0;
            while (!stack.isEmpty() && (node = stack.pop()) != null) {
                add(node.getData());
            }
        }

        /**
         * 冒泡排序
         */
        public void bubbleSort() {
            if (size <= 1) {
                return;
            }

            SingleListNode small = head;
            SingleListNode node = head.getNextNode();

            while (node != null) {
                if (node.getData() <= small.getData()) {

                    swap(small, node);
                }
                node = node.getNextNode();
            }
        }

        private void swap(SingleListNode node1, SingleListNode node2) {

        }

        private void print() {
            System.out.println("------------size:" + size);
            SingleListNode node = head;
            while (node != null) {
                System.out.println(node.getData());
                node = node.getNextNode();
            }
        }
    }

    static class SingleListNode {
        private int data;
        private SingleListNode nextNode;
        /**
         * 双向链表使用  上个节点指针
         */
        private SingleListNode lastNode;

        public SingleListNode(int data, SingleListNode next) {
            this.data = data;
            this.nextNode = next;
        }

        public void setData(int data) {
            this.data = data;
        }

        public void setNextNode(SingleListNode nextNode) {
            this.nextNode = nextNode;
        }

        public int getData() {
            return data;
        }

        public SingleListNode getNextNode() {
            return nextNode;
        }

        public SingleListNode getLastNode() {
            return lastNode;
        }

        public void setLastNode(SingleListNode lastNode) {
            this.lastNode = lastNode;
        }
    }

}
